package leetcode.sort;

/**
 * @author wangmaolin1
 * @date 2022/6/19 5:45 下午
 */
public class _215数组中的第k个最大元素 {
    public static void main(String[] args) {
        int[] nums = {3,2,1,5,6,4};
        System.out.println(new _215数组中的第k个最大元素().findKthLargest(nums,2));
    }

    public int findKthLargest(int[] nums, int k) {
        if (nums.length == 1) {
            return nums[0];
        }
        int len = nums.length;
        for (int i = nums.length / 2; i >= 0; i--) {
            perDown(nums, i, len);
        }
        for (int i = len - 1; i >= 0; i--) {
            swap(nums, i, 0);
            perDown(nums, 0, i);
        }
        return nums[k - 1];
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void perDown(int[] nums, int i, int len) {
        int temp;
        int child;
        for (temp = nums[i]; leftChild(i) < len; i = child) {
            child = leftChild(i);
            if (child != len - 1 && nums[child + 1] < nums[child]) {
                child++;
            }
            if (nums[child] < temp) {
                nums[i] = nums[child];
            }else {
                break;
            }
        }
        nums[i] = temp;
    }

    private int leftChild(int i) {
        return 2 * i + 1;
    }

}
